package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offerII_0071 {
    class Solution {
        List<Integer> pre;
        int len;
        int sum;
        public Solution(int[] w) {
            pre=new ArrayList<>();
            int len=w.length;
            this.len=len;
            int sum=0;
            for(int i=0;i<len;++i){
                sum+=w[i];
                pre.add(sum);
            }
            this.sum=sum;
        }

        public int pickIndex() {
            double tmp=sum*Math.random()+1;
            return search(0,len-1,tmp);
        }
        public int search(int left,int right,double tmp){
            if(left==right) return left;
            int mid=left+(right-left)/2;
            if(tmp-pre.get(mid)>=1) return search(mid+1,right,tmp);
            else if(tmp-pre.get(mid)<0) return search(left,mid,tmp);
            else return mid;
        }
    }
}
